# 第5节我要做月老——二分图最大匹配
# 时间复杂度O(NM)
# 二分图的定义是:如果一个图的所有顶点可以被分为X和两个集合，并且所有边的两个顶点恰好一个属于集合X，另一个属于集合Y，
# 即每个集合内的顶点没有边相连，那么此图就是二分图。

# 二分图-最大匹配算法(增广路:全部配对)

# 1.首先从任意一个未被配对的点u开始，从点u的边中任意选一条边（假设这条边是u→v)开始配对。如果此时点v还没有被配对，
# 则配对成功，此时便找到了一条增广路（只不过这条增广路比较简单)。
# 如果此时点v已经被配对了，那就要尝试进行“连锁反应”。如果尝试成功了，则找到一条增广路，此时需要更新原来的配对关系。
# 这里要用一个数组match来记录配对关系，比如点v与点u配对了，就记作match[v]-u和match[u]=v。配对成功后，记得要
# 将配对数加1。配对的过程我们可以通过深度优先搜索来实现，当然广度优先搜索也可以。

# 2如果刚才所选的边配对失败，要从点u的边中再重新选一条边，进行尝试。直到点u配对成功，或者尝试过点u所有的边为止。

# 3.接下来继续对剩下没有被配对的点一一进行配对，直到所有的点都尝试完毕，找不到新的增广路为止。

# 4.输出配对数。

e = [[0 for i in range(0, 102)] for i in range(0, 102)]
match = [0 for i in range(0, 102)]
book = [0 for i in range(0, 102)]
n, m = 0, 0
s = 0


def dfs(u):
    for i in range(1, n + 1):
        if book[i] == 0 and e[u][i] == 1:
            book[i] = 1  # 标记i已经被访问过
            # 如果i点未被配对或者找到了新的配对
            if match[i] == 0 or dfs(match[i]):
                # 更新配对关系
                match[i] = u
                match[u] = i
                return 1
    return 0


if __name__ == '__main__':
    print('start')
    n = 6
    m = 5
    a = [[1, 4], [1, 5], [2, 5], [2, 6], [3, 4]]
    for i, v in enumerate(a):
        e[v[0]][v[1]] = 1
        e[v[1]][v[0]] = 1
    # 遍历寻找配对
    for i in range(1, n + 1):
        # 清空上次搜索时的标记
        for j in range(1, n + 1):
            book[j] = 0
        if dfs(i):
            # 寻找增广路，如果找到，配对数加1
            s += 1
    print('%d' % s)
